The invention relates to computer networks, and particularly, to link state routing protocols used in computer networks.
Link state routing protocols such as open-shortest-path-first (“OSPF”) and intermediate-system-to-intermediate-system (“IS-IS”), using a shortest path first (“SPF”) routing, are commonly used interior gateway protocols (“IGP”) on the Internet. An IGP generally provides functionalities of the routing within an autonomous system (“AS”). A link state routing protocol typically divides an AS into multiple areas.
A router in an AS generally knows an operating topology of its area(s) and a cost to reach destinations outside its area(s) via area border routers. The router uses this information to determine the least cost (shortest) paths to different destinations. A design philosophy behind some currently deployed IGPs is to limit processing/bandwidth requirements of the protocol. Stability and robustness are prime concerns and the time the protocol takes to adjust to a change in the network topology (speed of convergence) is of secondary importance. Thus, when there is a change in the topology of the network (either a failure of a device or an addition of a new device to the topology), these protocols take an amount of transient time to converge to a new topology. During this transient time, network service may suffer serious deterioration in quality or may breakdown completely. Given the advent of new real-time applications over the Internet (e.g. voice over IP), a service deterioration/breakdown extending several tens of seconds can be considered intolerable.
A convergence to a topology change in the OSPF protocol includes the following steps: 1) detection of a topology change by the routers in the vicinity followed by the generation of new link state advertisements (“LSAs”) in response; 2) flooding of the new LSAs throughout the area network; and 3) routing table calculations by each router on receiving the LSAs, followed by distributing the routing table updates to the line cards.
In OSPF, the establishment and breakdown of an adjacency between two neighbor routers takes place via the Hello protocol. The Hello protocol requires a router to send Hello messages down its interfaces after every HelloInterval duration. After exchanging Hello messages, two neighbor routers synchronize their link state databases (“LSDBs”) before declaring adjacency to each other by originating new instances of their LSAs. Once established, an adjacency is maintained by periodic exchange of the Hello messages, and the LSDBs of the two routers stay synchronized via LSA flooding. The breakdown of an adjacency following a link or router failure is detected when a router does not receive a Hello message from its neighbor within a RouterDeadInterval. With the default values of a HelloInterval and the RouterDeadInterval (for example, 10 and 40 seconds respectively), the detection of a failure can take anywhere between 30 to 40 seconds. The affected routers declare breakdown of an adjacency by generating new instances of their LSAs. These newly generated LSAs are flooded throughout the OSPF area to which the failed adjacency belonged. Process of LSA generation and flooding can potentially be affected by minLSInterval, minLSAArrival, and/or RxmtInterval parameters defined in the OSPF standard as well as various non-standard LSA pacing delays. The minLSInterval and minLSAArrival parameters limit a frequency with which a router can originate new LSAs and accept new LSAs originated by others. The RxmtInterval determines a retransmission interval for a lost LSA. The LSA pacing delays, with a purpose to limit a link bandwidth consumption by LSA flooding, retransmission, or refresh process, introduce time gaps between consecutive LSUpdate packets (containing a plurality of LSAs) sent down an interface.
Recently, attention has been devoted to optimize the process of failure detection, adjacency establishment, LSA generation and flooding in link state routing protocols. For example, common link layers, such as packet over SDH or SONET (“POS”), can intimate a link failure to the router in few tens of milliseconds. For link layers with no such capability, bidirectional forwarding detection (“BFD”) provides a protocol and media independent method to achieve sub-second failure detection. Another way to reduce the failure detection time is to use a combination of reduced HelloInterval, and prioritized Hello messages.
For another example, rather than using a fixed value, commercial routers allow dynamic determination of minLSInterval value within a configurable range. To counter the impact of pacing delays on the convergence process, there have been proposals to push “important” LSAs out of an interface without incurring pacing delays and to use an adaptive retransmission scheme rather than a fixed LSA retransmission interval of 5 seconds. For yet another example, research done in the context of extending OSPF protocol for use in mobile adhoc networks (MANETs) have resulted in several competing technologies to reduce the need for adjacency establishment between neighbor routers, optimize the LSA flooding process and controlling the level of topology information flooded through the network.
On receiving a new LSA, a router has to update its routing table. The amount of work done in this process depends on the type of LSA received. As per OSPF standard, on receiving new router or network LSAs, the routing table is built again from scratch. This process involves calculating:                1) a plurality of intra-area routes for all OSPF areas to which the router belongs (typically using Dijkstra's shortest path algorithm on the contents of router and network LSAs),        2) the inter-area routes by examining the contents of all summary LSAs, and        3) the AS-external routes by examining the contents of all AS-external (“ASE”) LSAs.        
Typically, a router may have up to a few hundred router or network LSAs and up to a few thousand summary or ASE LSAs in its LSDB. Calculating intra-area routes using Dijkstra's algorithm (with a time complexity O(n×log(n))) typically takes only a few tens of milliseconds on modern routers. This time can be further reduced by using incremental algorithms rather than Dijkstra's algorithm. However, the examination of potentially several thousand summary or ASE LSAs may take several hundred milliseconds. Some commercial IS-IS implementations support a priority based scheme to process IP prefixes advertised by the IS-IS protocol. Under this scheme, the paths to the advertised prefixes are updated (and installed on the line cards) in order of their configured high, medium, or low priorities. OSPF may also benefit from a similar scheme to process important ASE LSAs before others.
A typical topology change, such as a failure of a router, may cause generation of several new LSAs (one for each router with which the failed router had an adjacency). These LSAs may not arrive simultaneously on a given router. If a router were to perform a routing table update immediately on receiving a new LSA, it may end up doing several such updates in close succession. As discussed earlier, a complete routing table update may take upto a few hundred milliseconds on modern router processors. Thus, several routing table updates in close succession may keep the router processor busy for a long time and cause failure to perform other important tasks such as timely generation and processing of Hello messages. It is possible that such failures may snowball into a complete meltdown of routing functionality. Hence, commercial routers typically do not perform a routing table update immediately on receiving a new LSA. For example, Cisco routers, with older internetworking operating system (“IOS”) releases, use a fixed value parameter spfHoldTime to limit the frequency of routing table updates to once per about 10 seconds. Additionally, there used to be an spfDelay (about 5 seconds) in doing a routing table update after receiving a new LSA. The spfDelay allows all the LSAs generated as a result of the topology change to arrive at the router before the routing table update.
In the following discussion, the above-identified scheme is referred to as fixed hold time scheme. While fixed spfDelay and spfHoldTime parameters limit the number of routing table updates and hence help avoid routing unstability, they also slow down the router's convergence to the new topology. With their default values (5 seconds for spfDelay and 10 seconds for spfHoldTime), a router may take anywhere between 5 to 15 seconds to converge to a topology change after receiving a new LSA. To balance the needs for fast convergence and routing stability, Cisco routers with post 12.2(14)S release IOS use a simple exponential backoff scheme to adjust the wait time between successive routing table updates. In this scheme, referred to as exponential backoff hold time (or exponential hold time) scheme in the following discussion, the wait time between successive routing table updates is initially set to a small value that increases exponentially with the frequency of received new LSAs. This scheme is described hereinafter.
Both fixed and exponential hold time schemes are effective in limiting the frequency of routing table updates in case of frequent (e.g. a flapping interface) and large scale (e.g. a network-wide router reboot and a shared risk link group (“SRLG”) failure) topology changes. While an exponential hold time scheme may provide faster convergence to isolated topology changes than a fixed hold time scheme, it is difficult to configure the scheme's parameters to achieve good performance (quick convergence with one or two routing table updates) for all possible isolated topology change scenarios in a network. A reason behind the OSPF protocol's apparent difficulty in achieving fast convergence to topology changes with minimum number of routing table updates is that the protocol uses individual LSAs as the trigger for routing table updates.
A simple exponential backoff scheme 100 to adjust the wait time (henceforth called spfHoldTime) between successive routing table updates is shown in FIG. 1. As shown in FIG. 1, a router is configured with the initial and maximum values for the spfHoldTime and a small value for spfDelay (an initial delay between a receipt of a new LSA and a first routing table update). Initially, the router is in INIT state 105 and moves to FIRST LSA state 110 on receiving a first new LSA. A change to the FIRST LSA state 110 is accompanied by the starting of a spfDelay timer. Any LSAs received while the router is in the FIRST LSA state 110 do not induce any action on part of the router since all these LSAs are assumed to be generated as a result of the same topology change as the first LSA. Once spfDelay is over, the router moves to a SPF state 115, performs a routing table update, and starts a spfHoldTime timer. At this point, the spfHoldTime has a pre-configured small initial value. If the spfHoldTime duration expires without a receipt of any more new LSAs, the router returns to the INIT state 110 with spfHoldTime still maintaining its small initial value. However, if the router receives a new LSA while in the SPF state 115, it moves to a SPF HOLD state 120, and causes the spfHoldTime value to be doubled (up to a pre-configured maximum limit; shown to be 10 seconds in FIG. 1). Since the move to SPF HOLD state 120 means that the router has already doubled the spfHoldTime value once after the last routing table update, any additional new LSAs received in the SPF HOLD state 120 do not cause any action to be taken. Once the spfHoldTime timer expires, the router moves back to the SPF state 115, performs a routing table update and restarts the spfHoldTime timer with a new value of spfHoldTime. A fixed hold time scheme can look similar to FIG. 1 except that the value of spfHoldTime does not change.
With reasonably small initial values for spfDelay and spfHoldTime, the exponential hold time scheme as shown in FIG. 1 may achieve quick convergence to an isolated topology change, especially when compared to the convergence time with fixed but large spfDelay or spfHoldTime values, with a small number of routing table updates. In case of frequent topology changes, the spfHoldTime is expected to quickly reach its maximum value thereby limiting the routing table update frequency. However, there exist some scenarios where this scheme may not be able to prevent several routing table updates in quick succession. This may happen if new LSAs arrive in such a manner that no LSA is received during the small spfHoldTime duration after the first routing table update. In this case, the router returns to the INIT state 105 after a first routing table update without ever doubling the spfHoldTime. Thus, the routing table update frequency can be much higher than expected. Even if the spfHoldTime increases to its maximum value, a small quiet period (equal to the maximum spfHoldTime value) causes the router to move back to the INIT state 105. A next set of LSAs may cause many SPF calculations to take place in quick succession before the spfHoldTime reaches its maximum value again.
Hence, significant attention has been given in the recent past to achieve fast convergence to topology changes in popular IGPs such as OSPF and IS-IS. As explained in the following sections, the process of convergence to a topology change (in OSPF and IS-IS) includes several steps. Recent research efforts have focused on reducing a plurality of delays contributed by individual steps to the overall convergence process. Often, there is a tradeoff involved between reducing delays and increasing processing or bandwidth overhead. While fast convergence to topology changes has emerged as a key requirement for next generation IGPs, a need for low processing overhead (which directly impacts the stability and robustness of the protocol) continue to be as important as before.
The invention provides a convergence process, namely the scheduling of the routing table calculations to be performed on receiving new link state advertisements (“LSAs”) originated by the routers directly affected by a topology change. Particularly, a new method, called LSA correlation, schedules routing table calculations in response to the LSAs received following a topology change. Significantly improved performance of the LSA correlation method (in terms of both convergence delay and processing overhead) is shown over existing methods. Although the OSPF protocol is used to describe LSA correlation and compare its performance with other methods, the proposed method and its performance evaluation results are relevant for other link state routing protocols as well.
LSA correlation is based on correlating a plurality of individual LSAs to identify topology changes that have caused their generation. The identification of a topology change triggers a routing table update. In the following, how to correlate the individual router and network LSAs to identify the topology changes is discussed. In this discussion, the term node refers to both a router and a transit network. The correlation process includes the following steps: identify an up, down or cost change subevent by iterating through the contents of the new LSA (and its old version); and correlate the subevents to identify a topology change. Every new router and network LSA needs to undergo this correlation task.
A link can be declared “down” as in link down if either end breaks adjacency with the other. A link can be declared “up” as in link up if both ends establish adjacency with each other. A node can be declared “down” as in router down if no node is currently adjacent to it. A node can be declared “up” as in router up if it establishes adjacency with all its known neighbors. A shared risk link group (“SRLG”) can be declared “down” as SRLG down if none of the links in the SRLG is “up.” A point-of-presence (“PoP”), which is basically a physical location where an internet service provider (“ISP”) has a bunch of routers in a rack, can be declared “down” as PoP down if it has no “up” out-of-pop links.
Since all the links in an SRLG share the same risk of failure, they fail together if the corresponding failure takes place. A common example of an SRLG is an optical fiber that carries a bunch of IP links. A cut in this fiber would cause all the links riding on the fiber to fail. Also, a PoP failure is the failure of a group of routers and hence treat it differently than an SRLG failure, which is typically the failure of a group of links. The information about the membership of the links and routers in SRLGs and PoPs could be flooded in the network via special LSAs.
LSA correlation depends on knowing if a router, an SRLG, or a PoP is in the process of “going down.” When a new LSA is received from a router, for example, router A, any “going down” marking is undone for router A and its PoP, and the number of “up” out-of-pop links of router A's PoP is updated. When an LSA from router A indicates the break down of its adjacency with a neighbor router B, and router B has not yet indicated the breakdown of this adjacency, LSA correlation checks if router B or its PoP (assuming that routers A and B belong to separate PoPs) or any of the SRLGs to which the link belongs is in the process of “going down.” If not, LSA correlation considers this event as a link failure and immediately schedule a routing table calculation so as to recover quickly from the link failure. Otherwise, LSA correlation considers the adjacency breakdown as part of a node/SRLG/PoP failure and mark router B, its PoP and all the SRLGs to which the link belongs as in the process of “going down.”
LSA correlation also (re)starts a timer, called doSPF. The purpose of doSPF timer is to incorporate all the pending LSAs into the routing table if topology changes cannot be identified within a certain time duration. The firing of this timer results in an immediate scheduling of routing table calculation and all the “going down” markings are undone. The number of “up” adjacencies of router B, “up” out-of-pop adjacencies of router B and its PoP, and “up” links in all the SRLGs to which link A:B belongs are decremented, and the router, the PoP, or an SRLG is declared to be down if the corresponding number reduces to zero. Declaration of a router, a SRLG, or a PoP failure is accompanied by immediate scheduling of a routing table calculation. In case of a PoP failure, all the routers in the PoP are marked as down.
When an LSA from router A indicates establishment of adjacency with router B, LSA correlation checks if router B already considers router A to be adjacent. If so, LSA correlation undoes any “going down” marking for the set of SRLGs to which link (A:B) belongs and increment the number of their “up” links. If any “going down” marking is undone for an SRLG, an immediate routing table calculation is scheduled. LSA correlation increments the number of adjacencies for routers A and B and start the doSPF timer unless it is already running. If both routers A and B are currently considered “up”, LSA correlation declares link (A:B) as “up.” Otherwise, LSA correlation considers this adjacency establishment as part of a router “up” event. If either of routers A or B is currently considered to be down, LSA correlation checks if it has established adjacency with all its neighbors and if so, declare the router to be “up.” The number of neighbors for a router can be determined by examining the router's LSA. Table I as shown in FIG. 3 shows different types of OSPF links and the information contained in an LSA for each link type. As shown, max(type 3 link states, type 1/2/4 link states) gives the number of neighbors for the router originating the LSA. LSA correlation counts only bidirectional adjacencies in the test for router up event since, in OSPF, the routing table update uses only those links where bidirectional adjacency exists between the two ends. The doSPF timer takes care of the possibility that a newly up router may not establish adjacency with all its neighbors. The firing of this timer causes a routing table calculation, thereby assimilating all the new LSAs received so far.
To avoid multiple routing table updates when multiple node up events take place in quick succession (e.g. a network-wide router reboot), LSA correlation keeps track of the list of the nodes that are in the process of coming up (a node can be considered in processing of coming up if it originates a new LSA but has not established adjacency with all its neighbors). Thus, the receipt of a new LSA from a node that is in the process of “coming up” causes its node ID to be inserted into a pendingNodes list. When a node has established adjacency with all its neighbors (i.e. is declared up), its ID is removed from the pendingNodes list, and a routing table calculation is performed if the pendingNodes list is now empty. With this optimization, LSA correlation can avoid multiple routing table updates in the event of multiple concurrent node up events. For safety, a pendingNodesTimer is started every time a routing table update is postponed because of non-empty pendingNodes list. If the pendingNodes list is still not empty when the timer pendingNodesTimer fires, a routing table update is performed to assimilate all recent node up events into the routing table.
Another optimization is to avoid routing table updates while the router is establishing adjacency with a neighbor. The correlation of the LSAs received during the link state database exchange may cause identification of several “topology changes”. Thus, without this optimization, a router may end up doing several routing table updates while establishing. LSA correlation can infer that a node is in the processing of coming up if it originates a new LSA but has not established adjacency with all its neighbors. adjacency with a neighbor. This optimization may keep the network topology discovered during the database exchange process from triggering routing table updates. Once the adjacency establishment process is over, the two newly adjacent routers can generate new LSAs, which when correlated cause a routing table update to take place.
Other aspects of the invention will become apparent by consideration of the detailed description and accompanying drawings.